package com.johann.classify;

import com.johann.test.SwapArray;

import java.util.Arrays;

// 将一个无序数组看成 两个数组，前一个数组只含第一个元素，为有序数组；后一个数组包含n-1个元素，为无需数组
//1 insertIndex >= 0 保证在insertVal找插入位置，不越界
//2 insertVal < arr[insertIndex] 待插入的数，还没找到插入位置
//3 就需要将arr[insertIndex]后移
// 插入排序
public class InsertSort {

    public  void insertSort(Integer [] arr){
        int insertVal=0;
        int insertIndex=0;
        // 进行n-1次循环  101 23 5 9 有点复杂
        for (int i = 1; i < arr.length; i++) {
            // 将下一个要插入的数 赋值 给 insertValue
            insertVal=arr[i];  // insertVal = 23
            insertIndex = i-1; // insertIndex = 0
            while(insertIndex>=0 && insertVal<arr[insertIndex]){
                arr[insertIndex+1] = arr[insertIndex];  // arr[1]=arr[0]  101 101 5 9
                System.out.println("第"+i+"次排序："+Arrays.toString(arr));
                insertIndex--;
            }
            //当退出while循环时，说明插入的位置已找到，此时的insert的位置已经越界了（要不然不会退出循环的），所以需要补1，insertIndex+1
            arr[insertIndex+1]=insertVal; // arr[-1+1] = 23

        }

    }

    // 更好理解
    public void insertSort02(Integer [] arr){
        for (int end = 1; end < arr.length; end++) {
            int newNumIndex = end;
            while (newNumIndex-1>=0 && arr[newNumIndex-1]>arr[newNumIndex]){
                new SwapArray(arr,newNumIndex-1,newNumIndex);
                newNumIndex--;
                System.out.println("第"+end+"次排序："+Arrays.toString(arr));
            }

        }
    }

    // 推荐这种插入排序，简单排序算法中，该方法最快，且样本小的时候推荐用
    public void insertSort03(Integer [] arr){
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j>0 && arr[j-1]>arr[j] ; j--) {
                new SwapArray(arr,j,j-1);
            }

        }
    }


}
